/* 

给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。


示例：
输入：nums = [3,0,1]
输出：2
解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。

*/

/* 
核心：
由题得：数组内每一项得取值是从区间[0,n]获得，而n是数组长度，所以数组内每一项的值应该也是索引值，[0,n]区间有n+1个数，所以找出在[0,n]中缺少的索引值即可


思路1：排序——排序后找出序号和元素不等的就是丢失的数

排序的时间复杂度是 O(nlogn)，遍历数组寻找丢失的数字的时间复杂度是 O(n)，因此总时间复杂度是 O(nlogn)。
空间复杂度：O(logn)，其中 n 是数组 nums 的长度。空间复杂度主要取决于排序的递归调用栈空间。

思路2：哈希集合
首先遍历数组 nums，将数组中的每个元素加入哈希集合，然后依次检查从 0 到 n 的每个整数是否在哈希集合中，

时间复杂度：O(n)，其中 n 是数组 nums 的长度。遍历数组 nums 将元素加入哈希集合的时间复杂度是 O(n)，遍历从 0 到 n 的每个整数并判断是否在哈希集合中的时间复杂度也是 O(n)。
空间复杂度：O(n)，其中 n 是数组 nums 的长度。哈希集合中需要存储 n 个整数。




进阶：你能否实现线性时间复杂度、仅使用额外常数空间的算法解决此问题?
*/

/**
 * @param {number[]} nums
 * @return {number}
 */
var missingNumber = function (nums) {
    const n = nums.length;
    // 思路1
    /* nums.sort((a, b) => a - b);
    for (let i = 0; i < n; i++) {
        if (nums[i] !== i) {
            return i;
        }
    }
    return n; */

    // 思路2
    let st = new Set()
    // 把每一项存储进set结构中
    for (let i = 0; i < n; i++) {
        st.add(nums[i])
    }
    // 遍历set是否有不存在的i
    for (let i = 0; i <= n; i++) {
        if (!st.has(i)) {
            return i
        }
    }

};

/* 

*/

// 运行
let nums = [9, 6, 4, 2, 3, 5, 7, 0, 1]
// let nums = [1]
let res = missingNumber(nums)
console.log(res);